#include <stdio.h>
#include <stdlib.h>

// 单链表结构
typedef struct node
{
    int data;
    struct node *next;
} linknode, *link;

// 函数声明
link Creat_link();
link Union(link la, link lb);

// 主函数
int main(void)
{
    // 创建单链表
    link H1 = Creat_link();
    link H2 = Creat_link();

    // 合并单链表
    link U = Union(H1, H2);

    return 0;
}

// 初始化单链表 终止数据为-1
link Creat_link()
{
    // 定义L为空列表
    link L = NULL;

    linknode *s;
    int x, flag = -1;
    scanf("%d", &x);
    // flag 为根据实际情况设定的结束数据输入的标志数据
    while (x != flag)
    {
        s = (linknode *)malloc(sizeof(linknode));
        // 申请结点,添加数据
        s->data = x;
        s->next = L;
        // 将结点s插入到链表头部
        L = s;
        scanf("%d", &x);
    }
    return L;
}

// 合并算法
link Union(link la, link lb)
{
    link L = NULL, p = NULL;
    p = (linknode *)malloc(sizeof(linknode));
    L = (linknode *)malloc(sizeof(linknode));
    while (la != NULL && lb != NULL)
    {

        if (la->data < lb->data)
        {
            p = la;
            la = la->next;
        }
        else
        {
            p = lb;
            lb = lb->next;
        }
        p->next = L->next;
        L->next = p;
    }
    while (la != NULL)
    {
        p = la;
        la = la->next;
        p->next = L->next;
        L->next = p;
    }
    while (lb != NULL)
    {
        p = lb;
        lb = lb->next;
        p->next = L->next;
        L->next = p;
    }

    return L;
}
